package leetcode_2301_2400;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class LeeCode_2328 {
    public static void main(String[] args) {
        System.out.println(countPaths2(new int[][]{{1, 1}, {3, 4}}));
    }
    private static int countPaths2(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        long mod = 1000_000_000 + 7, ans = 0;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(dp[i], -1);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans = (ans + dfs(grid, dp, i, j)) % mod;
            }
        }
        return (int) ans;
    }
    private static long dfs(int[][] grid, int[][] dp, int x, int y){
        if (dp[x][y] != -1){
            return dp[x][y];
        }
        long mod = 1000_000_000 + 7;
        int m = grid.length, n = grid[0].length;
        long res = 0;
        if (x - 1 >= 0 && grid[x - 1][y] > grid[x][y]){
            res += dfs(grid, dp, x - 1, y);
        }
        if (x + 1 < m && grid[x + 1][y] > grid[x][y]){
            res += dfs(grid, dp, x + 1, y);
        }
        if (y - 1 >= 0 && grid[x][y - 1] > grid[x][y]){
            res += dfs(grid, dp, x, y - 1);
        }
        if (y + 1 < n && grid[x][y + 1] > grid[x][y]){
            res += dfs(grid, dp, x, y + 1);
        }
        dp[x][y] = (int) ((res + 1) % mod);
        return dp[x][y];
    }

    private static int countPaths(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        long mod = 1000_000_000 + 7;
        long[][] dp = new long[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(dp[i], 1);
        }
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(o -> grid[o[0]][o[1]]));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                queue.add(new int[]{i, j});
            }
        }
        while (!queue.isEmpty()){
            int[] poll = queue.poll();
            int x = poll[0], y = poll[1];
            if (x - 1 >= 0 && grid[x - 1][y] > grid[x][y]){
                dp[x - 1][y] += dp[x][y];
                dp[x - 1][y] %= mod;
            }
            if (x + 1 < m && grid[x + 1][y] > grid[x][y]){
                dp[x + 1][y] += dp[x][y];
                dp[x + 1][y] %= mod;
            }
            if (y - 1 >= 0 && grid[x][y - 1] > grid[x][y]){
                dp[x][y - 1] += dp[x][y];
                dp[x][y - 1] %= mod;
            }
            if (y + 1 < n && grid[x][y + 1] > grid[x][y]){
                dp[x][y + 1] += dp[x][y];
                dp[x][y + 1] %= mod;
            }
        }
        long ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans += dp[i][j];
                ans %= mod;
            }
        }
        return (int) ans;
    }
}
